package com.breeze.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 3. 无重复字符的最长子串
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class LeetCode3 {
    // 该算法新新能较差原因是当判断包含了重复字符时，需要遍历删除集合中重复字符及以前的字符
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        List<Character> list = new ArrayList<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            while (list.contains(c)) {
                max = Math.max(max, list.size());
                if (list.size() > 0) {
                    list.remove(0);
                } else {
                    break;
                }
            }
            list.add(c);
        }
        max = Math.max(max, list.size());
        return max;
    }

    /**
     * 思路：滑动窗口，left指向滑动窗口左侧，当前遍历下标i为滑动窗口右侧
     *滑动窗口的最大大小
     */
    public int lengthOfLongestSubstring2(String s) {
        // 用于记录字符及对应的下标(并不是只包含滑动窗口中的字符)
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当包含这个字符时，需要更新滑动窗口的左下标
            if (map.containsKey(c)) {
                // 因为map中包含的字符可能在滑动窗口左侧，故取计算的左下标和原左下标的最大值
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, i);
            // 滑动窗口的大小为 i-left+1
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    public static void main(String[] args) {
        LeetCode3 leetCode3 = new LeetCode3();
        System.out.println(leetCode3.lengthOfLongestSubstring(" abcbefd"));
        System.out.println(leetCode3.lengthOfLongestSubstring2("abba"));
    }
}
